
// enum - full enumeration of knapsack solutions

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

FILE *fp;

int C; // capacity of the knapsack (total weight that can be stored)
int N;    // number of items available
int *w;      // array of item weights
int *v;      // array of item values (or profits)
int *kindex;  // array of indexes to the items
int QUIET=0; // can be set to 1 to suppress output during enumeration

extern void read_knapsack_instance(char *filename);
extern void print_instance();
extern void sort_by_ratio();
extern int print_sol2(int *s,  int *tv, int *tw);
void enumerate();
int next_binary(int *str, int N);


int main(int argc, char *argv[])
{
  read_knapsack_instance(argv[1]);
  print_instance();
  enumerate();
  return(0);
}

void enumerate()
{
  int i=0;
  int x[N];   // binary vector representing items packed
  int tv, tw; // total value and total weight of current knapsack solution
  int f;

  // set the knapsack initially empty
  for(i=0;i<N;i++)
    x[i]=0;

  QUIET=0;  // change this to 1 to suppress output

  while(!(next_binary(x, N)))
    {
 
      /* ADD CODE IN HERE TO KEEP TRACK OF FRACTION OF ENUMERATION DONE */

      f=print_sol2(x, &tv, &tw);  // calculates the value and weight and feasibility

      /* ADD CODE IN HERE TO KEEP TRACK OF BEST SOLUTION */
      
    }

  /* ADD CODE IN HERE TO PRINT OUT ONLY THE BEST SOLUTION */
 
  
}


int next_binary(int *str, int N)
{
  // Called with a binary string of length N, this 
  // function adds "1" to the string, e.g. 0001 would turn to 0010.
  // If the string overflows, then the function returns 1, else it returns 0.
  int i=N-1;
  while(i>=0)
    {
      if(str[i]==1)
	{
	  str[i]=0;
	  i--;
	}
      else
	{
	  str[i]=1;
	  break;
	}
    }
  if(i==-1)
    return(1);
  else
    return(0);

}
